#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
class Solution5
{
public:
    int coinChange(vector<int>& coins, int amount)
    {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        for (int i = 1;i <= amount;i++) dp[0][i] = -1;
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= amount;j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1] && dp[i][j - coins[i - 1]] != -1)
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        return dp[n][amount];
    }
};
class Solution
{
public:
    int numSquares(int n)
    {
        int cnt = 1;
        while ((cnt * cnt) < n) cnt++;
        vector<vector<int>> dp(cnt, vector<int>(n + 1));
        for (int i = 1;i <= n;i++) dp[0][i] = 0x3f3f3f3f;
        for (int i = 0;i < cnt;i++)
            for (int j = 0;j <= n;j++)
            {
                dp[i][j] = dp[i - 1][j];
                if ((j - i * i) >= 0) dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        return dp[cnt - 1][n];
    }
};
int main()
{
	vector<int> v = { 1,2,5 };
    /*Solution().coinChange(v, 11);*/
    Solution().numSquares(13);
	return 0;
}